{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "211dd546-2e74-4da2-b32a-e6780ab178f2",
   "metadata": {},
   "source": [
    "Apriori算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9e021cb6-5bb4-4f59-9b4d-4eb7143eae27",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构造单项集\n",
    "def createC1(dataSet):\n",
    "    C = []\n",
    "    for transaction in dataSet:\n",
    "        for item in transaction:\n",
    "            if [item] not in C:\n",
    "                C.append([item])\n",
    "    C.sort()\n",
    "    return list(map(frozenset,C))\n",
    "\n",
    "\n",
    "#计算Ck的项集在原始记录D中的支持度\n",
    "def scanD(D,Ck,minSupport):\n",
    "    ssCnt = {}\n",
    "    for tid in D:\n",
    "        for can in Ck:\n",
    "            if can.issubset(tid):\n",
    "                ssCnt[can] = ssCnt.get(can,0)+1\n",
    "    numItems = float(len(D))\n",
    "    retList = []\n",
    "    supportData = {}\n",
    "    for key in ssCnt:\n",
    "        support = ssCnt[key]/numItems\n",
    "        if support >= minSupport:\n",
    "            retList.insert(0,key)\n",
    "        supportData[key] = support\n",
    "    return retList,supportData\n",
    "\n",
    "# 生成新的候选项集\n",
    "def aprioriGen(Ck,k):\n",
    "    retList = []\n",
    "    lenCk = len(Ck)\n",
    "    for i in range(lenCk):\n",
    "        for j in range(i+1,lenCk):\n",
    "            L1 = list(Ck[i])[:k-2]\n",
    "            L2 = list(Ck[j])[:k-2]\n",
    "            L1.sort()\n",
    "            L2.sort()\n",
    "            if L1 == L2:\n",
    "                retList.append(Ck[i]|Ck[j])\n",
    "    return retList\n",
    "\n",
    "# 返回所有满足最小支持度的项集\n",
    "def apriori(D,minSupport):\n",
    "    C1=createC1(D)\n",
    "    L1,suppData = scanD(D,C1,minSupport)\n",
    "    L=[L1]\n",
    "    k=2\n",
    "    while (len(L[k-2])>0):\n",
    "        Ck = aprioriGen(L[k-2],k)\n",
    "        Lk,supK=scanD(D,Ck,minSupport)\n",
    "        suppData.update(supK)\n",
    "        L.append(Lk)\n",
    "        k+=1\n",
    "    return L,suppData\n",
    "\n",
    "# 满足最小置信度要求的规则\n",
    "def calcConf(freqSet,H,supportData,brl,minConf=0.7):\n",
    "    prunedH = []\n",
    "    for conseq in H:\n",
    "        conf=supportData[freqSet]/supportData[freqSet-conseq]\n",
    "        if conf >= minConf:\n",
    "            print(freqSet - conseq,'-->',conseq,'conf',conf)\n",
    "            brl.append((freqSet-conseq,conseq,conf))\n",
    "            prunedH.append(conseq)\n",
    "    return prunedH\n",
    "\n",
    "# 对频繁项集中元素超过2的项集进行合并\n",
    "def rulesFormConseq(freqSet,H,suppData,brl,minConf=0.7):\n",
    "    m = len(H[0])\n",
    "    if len(freqSet)>m+1:\n",
    "        Hmp1 = aprioriGen(H,m+1)\n",
    "        Hmp1 = calcConf(freqSet,Hmp1,suppData,brl,minConf)\n",
    "        if len(Hmp1)>1:\n",
    "            rulesFormConseq(freqSet,Hmp1,suppData,brl,minConf)\n",
    "\n",
    "# 根据频繁项集和最小可信度生产规则\n",
    "def generateRules(L,supportData,minConf=0.7):\n",
    "    bigRuleList=[]\n",
    "    for i in range(1,len(L)):\n",
    "        for freqSet in L[i]:\n",
    "            H1 = [frozenset([item]) for item in freqSet]\n",
    "            if i>1:\n",
    "                rulesFormConseq(freqSet,H1,supportData,bigRuleList,minConf)\n",
    "            else:\n",
    "                calcConf(freqSet,H1,supportData,bigRuleList,minConf)\n",
    "    return bigRuleList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6387cb93",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bdfaa25d-edc2-4d5c-8180-07b9c1fd6d59",
   "metadata": {},
   "outputs": [],
   "source": [
    "bRlist = generateRules(L1,suD2,0.1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
